/**
 * Created by L.jp
 * Description:
 *
 * 给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念：
 * 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max；
 * 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，
 * 就是arr的最小不可组成和； 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，
 * 那么max+1是arr的最小不可组成和；
 * 举例： arr = {3,2,5} arr的min为2，max为10，
 * 在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和；
 * arr = {3,2,4} arr的min为2，max为9，在区间[2,9]上，8是不能被任何一个子集相加得到的值中最小的，
 * 所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1，max为6
 * ，在区间[2,6]上，任何数都可以被某一个子集相加得到，所以7是arr的最小不可组成和；
 * 请写函数返回arr的最小不可组成和。
 * User: 86189
 * Date: 2022-03-26
 * Time: 18:44
 */
public class Solution {
    //这道题其实是一个动态规划的01背包问题，每一个数组元素就是物品，这个最小数组和，可以转换成我们要去最小不可能组成的背包和
    //从min~max中，我们需要从后面往前遍历，因为往背包里放物品，容量是会越来越小的，我们需要从大到小判断起
    public static  int getFirstUnFormedNum(int[] arr) {
        int minSum=Integer.MAX_VALUE;
        int maxSum=0;
        for(int i = 0; i < arr.length; i++){
            if(minSum>arr[i]){
                minSum = arr[i];
            }
            maxSum+=arr[i];
        }
        //定义一个布尔值的dp数组，下标从0~最大容量和，每一个数组下标代表背包容量，元素代表可不可以组成这个容量，如果无false就表示不可以
        boolean[] dp=new boolean[maxSum+1];//借助了容量为0的背包状态，表示为true
        //初始化
        dp[0]=true;
        //构造数组
        for(int i = 0;i<arr.length; i++){
            //我们从后面递推当前的状态，如果当前容量是可以组成的，那么当前容量减去当前物品的质量的这个容量和也是可以组成的
            for(int j=maxSum;j >=arr[i];j--){
                dp[j]=dp[j-arr[i]] || dp[j];
            }
        }
        //遍历状态数组
        for(int i = minSum;i<dp.length; i++){
            if(!dp[i]){
                return i;  //如果为false,表示不可组成这个容量和，找到了立马返回
            }
        }
        //反而如果都可以组成，那么就返回最大容量+1
        return  maxSum+1;
    }

    public static void main(String[] args) {
        int[] arr={2,3,5};
        System.out.println(getFirstUnFormedNum(arr));
    }
}
